package list

// https://leetcode-cn.com/problems/lru-cache/
// lru 队列
// 要求: 队列数量限制: capacity; get 和 put 都在 O(1) 复杂度之内完成
// 1 <= capacity <= 3000
// 0 <= key <= 10000
// 0 <= value <= 10^5
// 设计: key-value 使用数组存入（空间换时间），使用节点记录使用双向链表，链表的位置也记录在一个素组中
const (
	maxCacheSize = 10000
	notExistMark = -1
)

type LRUCache struct {
	keyValueMap []int
	capacity int
	len int
	nodeHead *DoublyNode
	nodeTail *DoublyNode
	nodeMap []*DoublyNode
}

// 提交前换回 Constructor
func LRUCacheConstructor(capacity int) LRUCache {
	head := new(DoublyNode)
	lru := LRUCache{
		keyValueMap: make([]int, maxCacheSize+1),
		len: 0,
		capacity: capacity,
		// 第一个节点不存数据
		nodeHead: head,
		nodeTail: head,
		nodeMap: make([]*DoublyNode, maxCacheSize+1),
	}
	// 默认不存在元素标记成 -1
	for index := 0; index <= maxCacheSize; index ++ {
		lru.keyValueMap[index] = notExistMark
	}
	
	return lru
}

// 获取: 需要完成 数据获取、最近使用节点往最前面移动 两个动作
func (cache *LRUCache) Get(key int) int {
	if cache.keyValueMap[key] != notExistMark {
		toMoveNode := cache.nodeMap[key]
		// 排除特殊情况: 当前节点已经是头部节点，就不需要移动
		if cache.nodeTail != toMoveNode {
			tail := cache.nodeTail
			toMoveNode.Pre.Next = toMoveNode.Next
			toMoveNode.Next.Pre = toMoveNode.Pre
			tail.Next = toMoveNode
			toMoveNode.Pre = tail
	
			cache.nodeTail = toMoveNode
		}
	}
	return cache.keyValueMap[key]
}

// 插入
// 元素存在: 直接赋值新元素，并放到队首
// 队列未满 且 元素不存在: 直接插入新元素，放到队首
// 队列已满: 删除 最久未使用的元素、插入元素
func (cache *LRUCache) Put(key int, value int)  {
	if value == notExistMark {
		return
	}
	if cache.keyValueMap[key] != notExistMark {
		currentNode := cache.nodeMap[key]
		currentNode.Val = value
		cache.keyValueMap[key] = value
		// 直接模拟一次查询，将节点移到最前面
		_ = cache.Get(key)
	} else if cache.len < cache.capacity {
		cache.innerPutNewElement(key, value)
	} else {
		// 删除元素
		toRemoveNode := cache.nodeHead.Next
		cache.nodeHead.Next = cache.nodeHead.Next.Next
		// 特殊情况: 当前就一个元素，那么 此时的 head->next 将会是空元素；另外 tail 尾部也需要转回头部
		if nil != cache.nodeHead.Next {
			cache.nodeHead.Next.Pre = cache.nodeHead
		} else {
			cache.nodeTail = cache.nodeHead
		}
		cache.keyValueMap[toRemoveNode.Key] = notExistMark
		cache.nodeMap[toRemoveNode.Key] = nil
		cache.len--

		// 再插入新元素
		cache.innerPutNewElement(key, value)
	}
}

func (cache *LRUCache) innerPutNewElement(key int, value int)  {
	node := &DoublyNode{Key: key, Val: value}
	node.Pre = cache.nodeTail
	cache.nodeTail.Next = node

	cache.nodeTail = node
	cache.nodeMap[key] = node
	cache.keyValueMap[key] = value

	cache.len++
}

// type DoublyNode struct {
//  Key int
// 	Val int
// 	Pre *DoublyNode
// 	Next *DoublyNode
// }

/**
 * Your LRUCache object will be instantiated and called as such:
 * obj := Constructor(capacity);
 * param_1 := obj.Get(key);
 * obj.Put(key,value);
 */